package priv.conceit.study.leetcode.simple.official;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * 编号100
 * 给定两个二叉树，编写一个函数来检验它们是否相同。
 * <a href="https://leetcode-cn.com/problems/same-tree"/>
 * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
 * 示例 1:
 *   1         1
 *  / \       / \
 * 2   3     2   3
 *
 * [1,2,3],   [1,2,3]
 *
 * 输出: true
 *
 * 示例 2:
 *    1          1
 *   /           \
 *  2             2
 *
 *   [1,2],     [1,null,2]
 * 输出: false
 *
 * 示例 3:
 *   1         1
 *  / \       / \
 * 2   1     1   2
 *
 *  [1,2,1],   [1,1,2]
 *
 * 输出: false
 *
 * 1-递归
 *
 * 2-双向队列
 * 两两比较
 *
 * @author Conceit
 * @since 1.0.0, 2019/7/18
 */
public class SameTree {

	public static void main(String[] args) {

	}

	public boolean isSameTree(TreeNode p, TreeNode q) {
		if(Objects.isNull(p)&&Objects.isNull(q)){
			return Boolean.TRUE;
		}
		if(Objects.isNull(p)||Objects.isNull(q)){
			return Boolean.FALSE;
		}
//		return deque(p, q);
		return recursion(p,q);
	}

	/**
	 * 递归
	 *
	 * @param p
	 * @param q
	 * @return
	 */
	public boolean recursion(TreeNode p, TreeNode q){
		boolean allIsNull=Objects.isNull(p)&&Objects.isNull(q);
		boolean difference=Objects.isNull(p)||Objects.isNull(q);

		if(allIsNull){
			return Boolean.TRUE;
		}
		if(difference){
			return Boolean.FALSE;
		}
		if(p.val!=q.val){
			return Boolean.FALSE;
		}
		return recursion(p.left,q.left)&&recursion(p.right,q.right);
	}

	/**
	 *
	 * 双向队列
	 *
	 *
	 * @param p
	 * @param q
	 * @return
	 */
	public boolean deque(TreeNode p, TreeNode q){

		Queue<TreeNode> queue1=new LinkedList<>();
		Queue<TreeNode> queue2=new LinkedList<>();

		//入队
		queue1.offer(p);
		queue2.offer(q);

		while (!queue1.isEmpty()&&!queue2.isEmpty()){
			//出队
			//poll 如果为空会返回null
			//removes 如果为空 会抛出异常
			TreeNode curTreeNode1=queue1.poll();
			TreeNode curTreeNode2=queue2.poll();

			if(Objects.isNull(curTreeNode1)&&Objects.isNull(curTreeNode2)){
				continue;
			}

			if(Objects.isNull(curTreeNode1)||Objects.isNull(curTreeNode2)){
				return Boolean.FALSE;
			}
			if(curTreeNode1.val!=curTreeNode2.val){
				return Boolean.FALSE;
			}
			queue1.offer(curTreeNode1.left);
			queue1.offer(curTreeNode1.right);

			queue2.offer(curTreeNode2.left);
			queue2.offer(curTreeNode2.right);
		}
		return Boolean.TRUE;
	}

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) { val = x; }
	}
}
